package jjn.round1;

/**
 * @author Jjn
 * @since 2022-08-16 15:11
 */
public class SortingAlgorithm_HeapSort implements SortAlgorithm {
    
    @Override
    public void sort(int... nums) {
        int length = nums.length;
        if (length == 0) {
            return;
        }
        for (int i = length / 2 - 1; i >= 0; i--) {
            heapify(nums, length, i);
        }
        for (int i = length - 1; i >= 0; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            heapify(nums, i, 0);
        }
    }
    
    private void heapify(int[] array, int length, int i) {
        int left = 2 * i + 1, right = 2 * i + 2;
        int largest = i;
        if (left < length && array[left] > array[largest]) {
            largest = left;
        }
        if (right < length && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;
            heapify(array, length, largest);
        }
    }
    
    @Override
    public String getName() {
        return "Heap sort";
    }
}
